// Copyright 2011 Jefferson Willian
// willmont7@gmail.com

#include <cstdio>
#include <algorithm>
#include <vector>

#define MAX 101
#define INF 1000000

using std::sort;
using std::vector;

/* Algoritmo de Dijkstra */
void dijkstra_solve(int matriz[][MAX], int dist[], int blocked[], int cnct[], int n, int x) {
  int ind;
  int lower = INF;

  blocked[x] = true;

  for (int i = 0;i < n;i++)
    if (!blocked[i])
      if (matriz[i][x] < dist[i]) {
        dist[i] = matriz[i][x];
        cnct[i] = x;
      }

  for (int i = 0;i < n;i++)
    if (!blocked[i] && dist[i] < lower) {
      lower = dist[i];
      ind = i;
    }

  if (lower == INF)
    return;

  dijkstra_solve(matriz, dist, blocked, cnct, n, ind);
}

void dijkstra(int matriz[][MAX], int cnct[], int n) {
  int blocked[MAX];
  int dist[MAX];

  for (int i = 0;i < n;i++) {
    dist[i] = INF;
    blocked[i] = false;
  }

  dist[0] = 0;

  dijkstra_solve(matriz, dist, blocked, cnct, n, 0);
}

/* Tipo aresta */
class Edge {
  public:
    int x;
    int y;
};

/* Compara dois tipos arestas */
bool compare(Edge a, Edge b) {
  if (a.x == b.x) {
    if (a.y <= b.y)
      return true;
    return false;
  }

  if (a.x <= b.x)
    return true;

  return false;
}

int main() {
  int n;
  int m;
  int entrada[3];
  int matriz[MAX][MAX];
  int cnct[MAX];
  vector<Edge> buffer;
  Edge t;
  int games = 1;

  while (scanf("%d%d", &n, &m) && (n != 0 || m != 0)) {
    /* Prepara as variaveis */
    buffer.clear();
    for (int i = 0;i < n;i++) {
      for (int j = 0;j < n;j++)
        matriz[i][j] = INF;
      cnct[i] = 0;
      matriz[i][i] = 0;
    }

    /* Recebe valores */
    for (int i = 0;i <m ;i++) {
      scanf("%d%d%d", &entrada[0], &entrada[1], &entrada[2]);
      matriz[entrada[0]-1][entrada[1]-1] = entrada[2];
      matriz[entrada[1]-1][entrada[0]-1] = entrada[2];
    }

    /* Resolve Dijkstra */
    dijkstra(matriz, cnct, n);

    /* Verifica quais sao as arestas */
    for (int i = 0;i < n;i++) {
      t.x = i < cnct[i]?i:cnct[i];
      t.y = i < cnct[i]?cnct[i]:i;
      buffer.push_back(t);
    }

    sort(buffer.begin(), buffer.begin()+n, compare);

    printf("Teste %d\n", games++);

    for (int i = 1;i < n;i++)
      printf("%d %d\n", buffer[i].x+1, buffer[i].y+1);

    printf("\n");
  }

  return 0;
}
